package com.kevinkk.tree;

/**
 * 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。
 * 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
 * <p>
 * BST 的插入还是很简单，中序遍历二叉树，大了就往右边插入，小了就往左边插入
 * 最后返回原来的根节点
 */

public class InsertIntoABinarySearchTree {
    class Solution {
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null) return new TreeNode(val);
            if (val < root.val) root.left = insertIntoBST(root.left, val);
            if (val > root.val) root.right = insertIntoBST(root.right, val);
            return root;
        }
    }
}
